package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/permutations/
 */
public class 全排列_46 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};
        System.out.println(new 全排列_46().permute(nums));

    }

    private int[] nums_;

    /**
     * 深度搜索
     * 看成是一颗树结构
     * 例如[1,2,3]
     * .        1                  2                3
     * .     2     3            .
     * .  3           2     .
     * 可以看成三颗数，每条路径即为答案
     * 需要记录每一层已经遍历过的索引，用新的list的对象来收集
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        nums_ = nums;
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < nums_.length; i++) {
            boolean[] nextRecords = new boolean[nums_.length];
            nextRecords[i] = true;
            List<Integer> nextList = new ArrayList<>();
            nextList.add(nums_[i]);
            dfs(nextRecords, nextList, lists);
        }
        return lists;
    }

    public void dfs(boolean[] records, List<Integer> curList, List<List<Integer>> lists) {
        if (curList.size() == nums_.length) {
            lists.add(curList);
            return;
        }
        for (int i = 0; i < nums_.length; i++) {
            if (records[i]) continue;
            boolean[] nextRecords = new boolean[nums_.length];
            System.arraycopy(records, 0, nextRecords, 0, nums_.length);
            nextRecords[i] = true;
            List<Integer> nextList = new ArrayList<>();
            for (int j = 0; j < curList.size(); j++) {
                nextList.add(curList.get(j));
            }
            nextList.add(nums_[i]);
            dfs(nextRecords, nextList, lists);
        }
    }

    // TODO 回溯？？？
}
